깊이 우선 탐색(DFS, Depth-First Search)은 그래프 이론에서 사용되는 탐색 알고리즘 중 하나로, 그래프의 모든 정점을 방문하는 방법을 말한다. DFS는 시작 정점에서 출발하여 한 경로를 따라 갈 수 있는 만큼 깊이 탐색한 후, 더 이상 갈 수 없게 되면 가장 최근에 만난 갈림길로 돌아와 다른 경로를 탐색하는 방식으로 동작한다. 이러한 방식은 재귀적으로 호출되거나 스택 자료구조를 사용하여 구현될 수 있다.

DFS의 시간 복잡도는 그래프가 인접 리스트로 표현된 경우 O(V + E), 인접 행렬로 표현된 경우 O(V^2)이다. 여기서 V는 그래프의 정점 수, E는 간선 수를 의미한다. DFS는 그래프가 연결되어 있는지를 판별하거나, 모든 경로를 탐색하거나, 사이클이 존재하는지 확인하는 등 다양한 문제 해결에 유용하게 활용된다.

DFS는 다음과 같은 단계로 수행된다:

1. 시작 정점을 방문하고, 스택(또는 재귀 호출)을 사용하여 현재 경로를 기록한다.

2. 현재 정점에서 연결된 다른 정점 중 아직 방문하지 않은 정점으로 이동하고, 이를 방문 처리한다.

3. 더 이상 이동할 수 없는 정점에 도달하면, 스택에서 이전 정점으로 되돌아간다.

4. 모든 정점을 방문할 때까지 이 과정을 반복한다.

이 알고리즘은 주로 그래프의 깊은 부분을 우선적으로 탐색하기 때문에, 넓은 부분을 우선적으로 탐색하는 너비 우선 탐색(BFS)과 대조된다. DFS는 비선형 자료 구조(트리, 그래프)에서 순회, 경로 찾기, 최단 경로 탐색 등에 사용되며, 백트래킹을 필요로 하는 문제 해결에도 많이 이용된다.